Given the root of a binary tree and an integer targetSum, return true if the tree has a root-to-leaf path such that adding up all the values along the path equals targetSum.
A leaf is a node with no children.
Example 1:
Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22 Output: true
Example 2:
Input: root = [1,2,3], targetSum = 5 Output: false
Example 3:
Input: root = [1,2], targetSum = 0 Output: false
Constraints:
- The number of nodes in the tree is in the range
[0, 5000]. -1000 <= Node.val <= 1000-1000 <= targetSum <= 1000
Average Rating: 4.64 (36 votes)
Solution
Binary tree definition
First of all, here is the definition of the TreeNode which we would use
in the following implementation.
Approach 1: Recursion
The most intuitive way is to use a recursion here.
One is going through the tree
by considering at each step the node itself and its children.
If node is not a leaf, one calls recursively hasPathSum method
for its children with a sum decreased by the current node value.
If node is a leaf, one checks if the the current sum is zero, i.e
if the initial sum was discovered.
Complexity Analysis
- Time complexity : we visit each node exactly once, thus the time complexity is O(N), where N is the number of nodes.
- Space complexity : in the worst case, the tree is completely unbalanced,
e.g. each node has only one child node, the recursion call would occur
N times (the height of the tree), therefore the storage to keep the call stack would be O(N).
But in the best case (the tree is completely balanced), the height of the tree would be log(N).
Therefore, the space complexity in this case would be O(log(N)).
Approach 2: Iterations
Algorithm
We could also convert the above recursion into iteration,
with the help of stack. DFS would be better than BFS here since
it works faster except the worst case. In the worst case the path root->leaf
with the given sum is the last considered one and in this case DFS results in
the same productivity as BFS.
The idea is to visit each node with the DFS strategy, while updating the remaining sum to cumulate at each visit.
So we start from a stack which contains the root node and the corresponding
remaining sum which is sum - root.val.
Then we proceed to the iterations: pop the current node out of the stack
and return True if the remaining sum is 0 and we're on the leaf node.
If the remaining sum is not zero or we're not on the leaf yet
then we push the child nodes
and corresponding remaining sums into stack.
Complexity Analysis
- Time complexity : the same as the recursion approach O(N).
- Space complexity : O(N) since in the worst case, when the tree is completely unbalanced, e.g. each node has only one child node, we would keep all N nodes in the stack. But in the best case (the tree is balanced), the height of the tree would be log(N). Therefore, the space complexity in this case would be O(log(N)).
January 6, 2019 2:53 AM
If a stack there then it is dfs
Bfs should use a queue
Last Edit: July 6, 2019 6:27 AM
For iteration version, it can also use pair:
public boolean hasPathSum(TreeNode root, int sum) {
LinkedList<Pair<TreeNode, Integer>> stack = new LinkedList<>();
stack.add(new Pair(root, sum));
while(!stack.isEmpty()){
Pair<TreeNode, Integer> p = stack.poll();
TreeNode node = p.getKey();
int remain = p.getValue();
if(node != null){
remain -= node.val;
if(node.left == null && node.right == null && remain == 0) return true;
stack.add(new Pair(node.left, remain));
stack.add(new Pair(node.right, remain));
}
}
return false;
}
December 28, 2018 12:58 PM
I'm pretty sure this is DFS
node, curr_sum = de.pop()
if node.right: de.append(node.right, curr_sum - node.right.val)
if node.left: de.append(node.left, curr_sum - node.left.val)
<--- this is DFS (preorder: root, left, right)
node, curr_sum = de.pop(0)
if node.left: de.append(node.left, curr_sum - node.left.val)
if node.right: de.append(node.right, curr_sum - node.right.val)
<--- this is BFS
April 14, 2020 7:13 AM
Terrible problem description: "Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum."
Consider the following initial conditions: "[], 0." This has no root, no leaves, and a zero sum. There is no root-to-leaf path.
The easy answer is "false." Since there is no root (much less any leaf), the result should be "false." However, this is inconsistent with this related problem, in which the lack of a root, and the lack of a leaf, isn't a problem.
https://leetcode.com/problems/minimum-depth-of-binary-tree/solution/
November 1, 2020 10:00 PM
Should be medium
May 7, 2020 10:08 AM
The recursive version is straightforward.
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
sum -= root.val;
if (root.left == null && root.right == null) return sum == 0;
return hasPathSum(root.left, sum) || hasPathSum(root.right, sum);
}
However the iterative version we have to do a bit more thinking. But remember, we can emulate recursion iteratively with the help of a stack.
public boolean hasPathSum(TreeNode root, int sum) {
if (root == null) return false;
Stack<TreeNode> treeStack = new Stack<>();
Stack<Integer> sumStack = new Stack<>();
treeStack.add(root);
sumStack.add(sum);
while (!treeStack.isEmpty()) {
TreeNode curr = treeStack.pop();
int currVal = sumStack.pop() - curr.val;
if (curr.left == null && curr.right == null && currVal == 0) return true;
if (curr.left != null) {
treeStack.push(curr.left);
sumStack.push(currVal);
}
if (curr.right != null) {
treeStack.push(curr.right);
sumStack.push(currVal);
}
}
return false;
}
Last Edit: December 31, 2020 7:38 AM
beats ~94%
Python3 BFS Solution
Instead of subtracting down to 0, I am adding up to the sum and checking that value on a leaf.
class Solution:
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root:
return False
q = [(root,root.val)]
while q:
node,v = q.pop(0)
if not node:
continue
if not node.left and not node.right:
if v == sum:
return True
continue
if node.left:
q.append((node.left,node.left.val + v))
if node.right:
q.append((node.right, node.right.val + v))
return False
November 3, 2020 5:01 AM
why would you need two stacks. Tree values can be mutated unless stated otherwise.
April 2, 2020 2:56 AM
May 4, 2021 11:50 AM
approach 1 is bottom up right? the return statement
return self.hasPathSum(root.left, sum) or self.hasPathSum(root.right, sum)
could only have been answered if we answered the subproblems at the leaves. then we carry the answer up. is this right?
xxxxxxxxxx/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */class Solution {public: bool hasPathSum(TreeNode* root, int sum) { if(root==NULL) return false; if(root->left == NULL && root->right == NULL && root->val == sum) return true; sum = sum-root->val; if(hasPathSum(root->left, sum) || hasPathSum(root->right, sum)) return true; return false; }};